use std::cmp::min;
use std::collections::HashMap;

struct Solution {}

fn main() {}

impl Solution {
    pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let nums1_map: HashMap<i32, i32> = Self::build_cnt_map(&nums1);
        let nums2_map: HashMap<i32, i32> = Self::build_cnt_map(&nums2);

        let mut ret: Vec<i32> = vec![];
        for x in nums1_map.keys() {
            if nums1_map.contains_key(x) && nums2_map.contains_key(x) {
                let cnt = min(nums1_map.get(x).unwrap(), nums2_map.get(x).unwrap());
                Self::add_to_vec(&mut ret, x, cnt);
            }
        }
        ret
    }

    fn build_cnt_map(nums: &Vec<i32>) -> HashMap<i32, i32> {
        let mut ret: HashMap<i32, i32> = HashMap::new();
        nums.iter().for_each(|e| {
            if ret.contains_key(e) {
                ret.insert(e.to_owned(), *ret.get(e).unwrap() + 1);
            } else {
                ret.insert(e.to_owned(), 1);
            }
        });
        ret
    }

    fn add_to_vec(ret: &mut Vec<i32>, ele: &i32, cnt: &i32) {
        for idx in 0..cnt.to_owned() {
            ret.push(ele.to_owned());
        }
    }
}